package com.atguigu.linkedlist;

public class JosephuDemo {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoys(5);
        circleSingleLinkedList.showBoys();

        circleSingleLinkedList.countBoys(1,6,5);
    }
}


class CircleSingleLinkedList{
    private Boy first=null;

    public void addBoys(int num){
        if(num<1){
            System.out.println("非法数字:"+num);
            return;
        }
        if (num==1) {
            Boy boy = new Boy(num);
            first=boy;
            first.setNext(boy);
        }else{
            Boy curBoy=null;
            for (int i = 1; i <= num; i++) {
                Boy boy = new Boy(i);
                if (i==1) {
                    first=boy;
                    first.setNext(boy);
                    curBoy=first;
                }else{
                    curBoy.setNext(boy);
                    boy.setNext(first);
                    curBoy=boy;
                }
            }
        }
    }

    public void showBoys(){
        if (first==null) {
            System.out.println("环形链表为空");
            return;
        }
        Boy curBoy=first;
        while(true){
            System.out.println(curBoy.getNo());
            if (curBoy.getNext()==first) {
                break;
            }
            curBoy=curBoy.getNext();
        }

    }

    public Boy calcLastBoy(){
        if (first==null) {
            throw new RuntimeException("初始节点不能为空");
        }

        Boy helper=first;
        do {
            helper = helper.getNext();
        } while (helper.getNext() != first);
        return helper;
    }

    public Boy skip(Boy helper,int skipNum){
        for (int i = 0; i < skipNum-1; i++) {
            helper=helper.getNext();
        }
        first=helper.getNext();
        return helper;
    }

    public void remove(Boy helper){
        System.out.printf("第%d个小孩出圈\n",first.getNo());
        first=first.getNext();
        helper.setNext(first);
    }

    public void countBoys(int startNo,int skipNum,int circleSize){
        // 创建辅助指针, 指向初始节点的上一个节点
        Boy helper = calcLastBoy();

        // 辅助指针与初始指针, 同时跳转(skipNum-1)次, 此时的first节点就是待出圈的节点


        // 遍历skip+remove操作, 直到剩下一个节点, 即helper==first
        while(helper!=first){
            helper=skip(helper,skipNum);
            remove(helper);
        }
        System.out.printf("最后的小孩是%d\n",first.getNo());
    }
}

class Boy{
    private Integer no;
    private Boy next;

    public Boy(Integer no) {
        this.no = no;
    }

    public Integer getNo() {
        return no;
    }

    public void setNo(Integer no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}